package cn.lbd.arithmetic.sort;

import org.junit.Test;

import java.util.Arrays;

/**
 * 基数排序
 * */
public class RadixSort {

    private static void sort(int[] array) {
        //桶的数组  为防止溢出，每个桶的大小取数组长度  空间换时间
        int[][] bucket =new int[10][array.length];
        //桶的计数器数组 bucketCounts[i]表示第i个桶的计数器
        int[] bucketCounts=new int[10];
        //获取数组中的最大元素
        int max = array[0];
        for (int arr = 1; arr < array.length; arr++) {
            if(max<array[arr]){
                max=array[arr];
            }
        }
        //最大元素的位数
        int maxLength = (max +"").length();
        for (int i = 0,n = 1; i < maxLength; i++,n*=10) {
            //将原数组的数据放入桶
            for (int j = 0; j < array.length; j++) {
                //个位上的值
                int digitOfElement=array[j] / n % 10;
                bucket[digitOfElement][bucketCounts[digitOfElement]]=array[j];
                //放入一个元素，计数器加1
                bucketCounts[digitOfElement]++;
            }
            //将桶中数据按顺序放回原数组
            int index = 0;
            for (int k = 0; k < bucketCounts.length; k++) {
                //某个桶中没有数据，则不需要管它
                if(bucketCounts[k] != 0){
                    for (int l = 0; l < bucketCounts[k]; l++) {
                        array[index++] = bucket[k][l];
                    }
                }
                //每次操作结束后，把计数器清0，以免影响下次操作
                bucketCounts[k]=0;
            }
        }
    }


    public static void main(String[] args) {
        int[] array={177,3,253,14,11,9};
        sort(array);
    }


    //800万数据0.464
    @Test
    public void batchTest(){
        int[] arr = new int[8000000];
        for(int i =0; i < 8000000;i++) {
            arr[i] = (int)(Math.random() * 8000000);
        }

        long start = System.currentTimeMillis();

        sort(arr);

        long end = System.currentTimeMillis();

        System.out.println((double)(end-start)/1000);
    }
}
